package TestDemo;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode() {
    }
}

public class MyBinaryTree {

    TreeNode root;    // 指向二叉树的根节点

    // 自己手动快速创建一棵二叉树
    public TreeNode createBinaryTreeN(){
        // write code here
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        root = a;
        return root;
    }

    // 将递归方式再包装一层
    public void preOrder(){
        System.out.print("前序遍历:");
        preOrder(root);
        System.out.println();
    }

    public void inOrder(){
        System.out.print("中序遍历:");
        inOrder(root);
        System.out.println();
    }

    public void postOrder(){
        System.out.print("后序遍历:");
        postOrder(root);
        System.out.println();
    }

    public int size(){
        return size(root);
    }

    public int getLeafNode(){
        return getLeafNode(root);
    }

    public int getKLevelNode(int k){
        return getKLevelNode(root, k);
    }

    public int height(){
        return height(root);
    }

    public TreeNode find(int data){
        return find(root, data);
    }

    public void levelOrder(){
        // write code here
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            if (treeNode != null){
                System.out.print(treeNode.val + " ");
                queue.offer(treeNode.left);
                queue.offer(treeNode.right);
            }
        }
    }

    public boolean isCompleteTree(){
        // write code here

        return true;
    }


    // 前序遍历 - 操作：指的是对节点中的值域进行打印
    private void preOrder(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return;
        System.out.print(treeRoot.val + " ");
        preOrder(treeRoot.left);
        preOrder(treeRoot.right);
    }

    // 中序遍历 - 操作：指的是对节点中的值域进行打印
    private void inOrder(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return;
        inOrder(treeRoot.left);
        System.out.print(treeRoot.val + " ");
        inOrder(treeRoot.right);
    }

    // 后序遍历 - 操作：指的是对节点中的值域进行打印
    private void postOrder(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return;
        postOrder(treeRoot.left);
        postOrder(treeRoot.right);
        System.out.print(treeRoot.val + " ");
    }

    // 获取二叉树中节点的个数
    private int size(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return 0;
        return size(treeRoot.left) + size(treeRoot.right) + 1;
    }

    // 获取二叉树中叶子节点的个数
    private int getLeafNode(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return 0;
        if (treeRoot.left == null && treeRoot.right == null) return 1;
        return getLeafNode(treeRoot.left) + getLeafNode(treeRoot.right);
    }

    // 获取二叉树中第k层节点个数----注意：认为根就在第1层
    private int getKLevelNode(TreeNode treeRoot, int k){
        // write code here
        if (treeRoot == null) return 0;
        if (k == 1) return 1;
        return getKLevelNode(treeRoot.left,k-1) + getKLevelNode(treeRoot.right,k-1);
    }

    // 获取树的高度
    private int height(TreeNode treeRoot){
        // write code here
        if (treeRoot == null) return 0;
        return Math.max(height(treeRoot.left),height(treeRoot.right)) + 1;
    }

    // 查找值为data的节点，并返回
    private TreeNode find(TreeNode treeRoot, int data){
        // write code here
        if (treeRoot == null) return null;
        if (treeRoot.val == data) return treeRoot;
        TreeNode left = find(treeRoot.left,data);
        TreeNode right = find(treeRoot.right,data);
        return left != null ? left : right;
    }
}
